#include <iostream>
using namespace std;

// 定义单链表节点结构体
struct ListNode {
    char data; // 存储节点数据
    ListNode* next; // 指向下一个节点的指针
};

// 初始化单链表
ListNode* initList() {
    ListNode* head = nullptr; // 初始化头节点为空
    return head;
}

// 尾插法插入元素
void insertTail(ListNode* head, char value) {
    ListNode* newNode = new ListNode(); // 创建新节点
    newNode->data = value; // 赋值节点数据
    newNode->next = nullptr; // 初始化下一个节点为空

    if (head == nullptr) { // 如果头节点为空，则将新节点作为头节点
        head = newNode;
    } else { // 否则，将新节点插入到链表尾部
        ListNode* cur = head;
        while (cur->next != nullptr) { // 找到链表最后一个节点
            cur = cur->next;
        }
        cur->next = newNode; // 将新节点插入到链表尾部
    }
}

// 输出单链表
void printList(ListNode* head) {
    ListNode* cur = head; // 初始化当前节点为头节点
    while (cur != nullptr) { // 当当前节点不为空时
        cout << cur->data << " "; // 输出当前节点数据
        cur = cur->next; // 将当前节点指向下一个节点
    }
    cout << endl; // 输出换行
}

// 输出单链表长度
int lengthList(ListNode* head) {
    int len = 0; // 初始化长度为 0
    ListNode* cur = head; // 初始化当前节点为头节点
    while (cur != nullptr) { // 当当前节点不为空时
        len++; // 长度加 1
        cur = cur->next; // 将当前节点指向下一个节点
    }
    return len; // 返回长度
}

// 判断单链表是否为空
bool isEmptyList(ListNode* head) {
    return head == nullptr; // 如果头节点为空，则链表为空
}

// 输出单链表第 index 个元素
void printElement(ListNode* head, int index) {
    ListNode* cur = head; // 初始化当前节点为头节点
    for (int i = 0; i < index; i++) { // 找到第 index 个节点
        if (cur == nullptr) { // 如果找不到第 index 个节点，则输出"找不到该元素"
            cout << "找不到该元素" << endl;
            return;
        }
        cur = cur->next; // 将当前节点指向下一个节点
    }
    if (cur != nullptr) { // 如果找到第 index 个节点
        cout << cur->data << endl; // 输出第 index 个节点的数据
    }
}

// 输出元素 a 的位置
int searchElement(ListNode* head, char value) {
    ListNode* cur = head; // 初始化当前节点为头节点
    int index = 0; // 初始化索引为 0
    while (cur != nullptr) { // 当当前节点不为空时
        if (cur->data == value) { // 如果当前节点数据等于目标元素
            return index; // 返回索引
        }
        index++; // 索引加 1
        cur = cur->next; // 将当前节点指向下一个节点
    }
    return -1; // 如果找不到目标元素，则返回-1
}

int main() {
    ListNode* head = initList(); // 初始化单链表

    // 尾插法插入元素
    insertTail(head, 'a');
    insertTail(head, 'b');
    insertTail(head, 'c');
    insertTail(head, 'd');
    insertTail(head, 'e');

    // 输出单链表
    cout << "单链表: ";
    printList(head);

    // 输出单链表长度
    cout << "单链表长度: " << lengthList(head) << endl;

    // 判断单链表是否为空
    cout << "单链表是否为空: " << (isEmptyList(head)? "是" : "否") << endl;

    // 输出单链表第 3 个元素
    printElement(head, 2);

    // 输出元素 a 的位置
    cout << "元素 'a' 的位置: " << searchElement(head, 'a') << endl;

    return 0;
}
